ATM is a networking protocol which supports a variety of applications having distinct bandwidth requirements and distinct tolerances for delay, jitter, cell loss, etc. ATM networks provide different "service classes" at different prices which reflect the differing quality of service (QoS) provided by each class. The QoS can define minimum levels of available bandwidth, and place bounds on parameters such as cell loss and delay. The user informs the network, upon connection set-up, of the expected nature of the traffic to be sent by the user along the connection, and of the QoS required for such connection.
The ABR service class supports variable rate data transmissions without preserving timing relationships between source and destination. ABR users are provided guaranteed service with respect to cell loss, and "fair" access to available bandwidth as determined by predefined fairness criteria. The user receives only the network's best attempt to maximize the user's available bandwidth or allowed cell rate (ACR), through the use of feedback flow control mechanisms. Such mechanisms facilitate control over the amount of traffic allowed into the network, and hence minimization of cell loss due to congestion. A traffic shaping algorithm, controlling the ACR, is used at the source to control the traffic rate into the network, based upon a congestion indicator in the received cells.
Pre-defined traffic parameters characterize the traffic sent over an ATM connection. Parameters such as minimum cell rate (MCR), peak cell rate (PCR), cell delay variation tolerance (CDVT), sustainable cell rate (SCR) and burst tolerance (BT) characterize the traffic stream in general, although not all parameters are meaningful for all service classes. For example, in ABR service, the PCR determines the maximum value of the ACR, which is dynamically controlled by the ATM network, using congestion control mechanisms, to vary between the MCR and PCR.
When setting up a connection, the requesting node informs the network of the required service class, the traffic parameters of the data to be passed in each direction along the connection, and the QoS requested for each direction. Establishment of an ATM connection having specified traffic descriptors constitutes a traffic "contract" between the user and the network. The network offers a QoS guarantee appropriate to the service class requested by the user. In return, the user must confine traffic sent over the connection in compliance with the attributes of the traffic contract for the requested service class. ATM network switches police the user's traffic via algorithms which determine whether the cell stream is compliant with the traffic contract.
An ABR scheduler is an essential and integral part of any ATM implementation offering ABR service. Its purpose is to determine when cells are ready to be transmitted in a fair and efficient manner. In this context, "fairness" means that all service classes should be given an equal opportunity; "efficiency" means that cells should be transmitted at or near their specified rates. U.S. application Ser. No. 08/622,398 (hereafter "the '398 application") which is hereby incorporated by reference, describes the implementation of an ABR scheduler having the necessary attributes of fairness and efficiency.
In an ATM network, a communication channel may be characterized by a virtual circuit (VC) defined by pre-selected traffic and QoS parameters. The problem, in providing ABR service, is to efficiently manage transmission of cells pertaining to different VCs. The allowed cell rate (ACR) at which a cell belonging to a given VC is transmitted varies between the minimum cell rate (MCR) and the peak cell rate (PCR), which are negotiated when the VC is established. The ACR is a floating point number as defined in the ATM Forum specifications, and expressed as ##EQU1## where 0.ltoreq.e.ltoreq.31 and 0.ltoreq.m.ltoreq.511. ACR covers a wide dynamic range between 1 cell/sec to 32 Gigacells/sec.
In order to permit efficient scheduling of VCs in an ABR service, the ABR scheduler described in the '398 application uses a classification scheme in which VCs are indexed according to their exponents and mantissa to form groups of "profiles" and "sub-profiles". More particularly, a profile i, 1.ltoreq.i.ltoreq.p is a collection of VCs whose ACRs fall within a closed range: ##EQU2## where p is the number of profiles, sp is the number of sub-profiles, and 0.ltoreq.x&lt;1/sp such that the effective profile rate is then given by 2.sup.p-i. A sub-profile j, 1.ltoreq.j.ltoreq.sp is a subset of VCs belonging to profile i, 1.ltoreq.i.ltoreq.p such that their ACRs default to the nearest and smaller rate given by: ##EQU3## For example, if p=sp=4 then the sub-profile rates conforming to the above definition are summarized in Table 1.
TABLE 1 ______________________________________ Sub-profile rates (cells/second) Profile 1 2 3 4 ______________________________________ 1 8 7 6 5 2 4 3.5 3 2.5 3 2 1.75 1.50 1.25 4 1 0.875 0.750 0.625 ______________________________________
Note that the rates of sub-profile 1 in each of the four profiles are identical to the profile rates of 8, 4, 2 and 1 respectively. It can be seen that the larger the number of sub-profiles, the finer the granularity and therefore the VCs will be scheduled closer to their ACRs, consequently increasing hardware and computational requirements.
Whenever a VC is provisioned (i.e. allocated), the ACR of the corresponding VC is uniquely mapped to one of the closest and smallest profile/sub-profile rates. The smaller rate is chosen, since otherwise the negotiated traffic contract may be violated by scheduling a cell at a rate faster than the ACR.
By quantizing VCs based on the exponent values of their rates, a fast deterministic search can be performed to service the profiles. A linear search on the sub-profiles is then conducted and, using a virtual time algorithm wherein the next cell time is calculated based on its ACR, the system clock frequency and the number of profiles, it can be uniquely determined whether the chosen VCs are ready for transmission by comparing with the current cell time.
The ABR scheduler of the '398 application also maintains a table (in memory) in which VCs are stored along with negotiated traffic contract parameters such as PCR, MCR, etc. A linked list of VCs is attached to each profile/sub-profile. When a particular profile/sub-profile is ready to be transmitted (as determined by the scheduler algorithm summarized above), the entire list linked to that profile/sub-profile is serviced and the ATM cells are placed in the ABR output queue for transmission.
The scheduler also interacts with an ABR contract module which implements source/destination behaviour functions in accordance with ATM Forum-defined congestion management protocols and links/delinks the VCs to the various profiles/sub-profiles in the table dynamically, depending on its state. For example, if congestion is detected in the network, then the ACR for a particular VC is reduced by a predetermined amount and accordingly the VC's link to a profile/sub-profile needs to be updated.
The ABR scheduler described in the '398 application assumes a negotiated zero MCR for all VCs, and assumes an available bandwidth equal to the full line rate. By quantizing the ACR into a finite subset of traffic profiles to which the provisioned VCs are attached, the ABR scheduler of the '398 application searches and outputs a sequence of traffic profile addresses. For each element in this sequence, all VCs that are attached to the selected traffic profile are scanned linearly and dispatched to the output.
The ABR scheduler of the '398 application performs well statistically, according to the rate weighted bandwidth distribution scheme for different degrees of provisioning (i.e., under, equal or over provisioned cases). However, it suffers from the problem of "cell clumping" for the equal and under provisioned cases, due to the aforementioned linear scanning of each link list. For these two cases, cell clumping occurs when VCs whose ACRs are lower than the peak bandwidth are scheduled at the line rate. The size of each such burst is dependent on the number of VCs attached to the given traffic profile in the link list. The longer the link list, the greater the burst length (cell clumping). Consequently, buffer overflows may occur in downstream ATM switches and/or at the destination. Avoidance and/or reduction of such overflows is of paramount importance.
The ABR scheduler of the '398 application does not suffice for ABR connections requiring non-zero MCR support and accordingly cannot provide a minimum guaranteed bandwidth; nor does the '398 application's scheduler accomodate VC buffer overflow. The present invention addresses these shortcomings in a manner which satisfies the efficiency and fairness criteria for bandwidth allocation. The present invention also provides a flexible arbitration scheme for mixing ATM cells of various traffic sources such as ABR, unspecified bit rate (UBR), variable bit rate (VBR) and constant bit rate (CBR), such that the relative proportion of each stream can be varied as desired.